package com.cise.lire.ParallelSearcher.sort.linear;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import com.cise.lire.ParallelSearcher.sort.ISort;
import com.cise.lire.ParallelSearcher.utils.IResult;
import com.cise.lire.ParallelSearcher.utils.Result;

public class LinearSort extends ISort {
	private double[] featureWeight = null;
	
	public LinearSort(double[] featureWeight) {
		this.featureWeight = featureWeight;
	}

	@Override
	public ArrayList<IResult> sort(ArrayList<IResult[]> results) {
		if(results == null) return null;
		ArrayList<IResult> result = new ArrayList<IResult>();
		ArrayList<Double> distances = new ArrayList<Double>();
		ArrayList<Double> average = new ArrayList<Double>();
		
		// 求得均值
		for (int i = 0; i < results.size(); i++) {
			IResult[] iResult = results.get(i);
			if (iResult == null) {
				average.add(0.0);
			}
			double sum = 0;
			for (int j = 0; j < iResult.length; j++) {
				sum += iResult[j].getDistance();
			}
			average.add(sum / iResult.length);
		}

		// 遍历所有结果
		for (int i = 0; i < results.size(); i++) {
			IResult[] iResults = results.get(i);
			if(iResults == null) continue;
			for (int j = 0; j < iResults.length; j++) {
				// 如果当前结果未添加进结果列表中
				int index = iResults[j].indexInList(result);
				if (index < 0) {
					result.add(iResults[j]);
					distances.add(this.featureWeight[i] * (10 - iResults[j].getDistance() / average.get(i)));
				}
				// 如果已添加
				else {
					double weight = distances.get(index);
					distances.set(index, weight+this.featureWeight[i] * (10 - iResults[j].getDistance() / average.get(i)));
				}
			}
		}
		
		// 将新的距离作为结果的距离
		for (int i = 0; i < result.size(); i++) {
			result.get(i).setDistance(distances.get(i));
		}
		
		return sortWithWeight(result);
	}

	/**
	 * 根据距离排序 以下使用堆排序<br>
	 * 
	 * @param result
	 * @param distances
	 * @return
	 */
	@Override
	protected ArrayList<IResult> sortWithWeight(ArrayList<IResult> result) {
		int size = result.size();
		for (int i = 0; i < size; i++) {
			// 还需要排序的节点数
			int s = size - i;
			for (int j = s / 2 - 1; j >= 0; j--) {
				// 左右子树中距离较大的若为左子树，则max等于0（默认），若为右子树则max则为1
				int max = 0;
				if (2 * j + 2 < s
						&& result.get(2 * j + 1).getDistance() > result.get(2 * j + 2).getDistance()) {
					max = 1;
				}
				if (max == 0) {
					// 父节点的距离小于左子树距离
					if (result.get(j).getDistance() > result.get(2 * j + 1).getDistance()) {
						Collections.swap(result, j, 2 * j + 1);
					}
				} else {
					// 父节点的距离小于右子树距离
					if (result.get(j).getDistance() > result.get(2 * j + 2).getDistance()) {
						Collections.swap(result, j, 2 * j + 2);
					}
				}
			}
			// 堆顶为未排序的节点中的最大值
			// 堆顶与未排序的最后一个节点互换
			Collections.swap(result, 0, s - 1);
		}
		return result;
	}
}
